package Lee_code;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Lee_496
{
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        stack.push(0);
        for (int i=1; i<nums2.length; i++)
        {
            if(!stack.isEmpty() && nums2[i] < nums2[stack.peek()])
            {
                stack.push(i);
            }
            else
            {
                while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()])
                {
                    map.put(nums2[stack.peek()], nums2[i]);
                    stack.pop();
                }
                stack.push(i);
            }
        }
        int[] res = new int[nums1.length];
        for(int i=0; i< nums1.length; i++)
        {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}
